package own.stu.jobgib.playown.alg.solution.dp;

/**
 * 博弈型dp
 * <li>博弈为两方游戏</li>
 * <li>一方先下，在一定规则下依次出护</li>
 * <li>如果满足一定条件，则一方胜</li>
 * <li>目标:取胜</li>
 */
public class GamblingType {
    public static void main(String[] args) {
        GamblingType g = new GamblingType();
//        System.out.println(g.firstWillWin(5));
        System.out.println(g.firstWillWin(new int[]{1, 2, 4, 7}));
        System.out.println(g.firstWillWin(new int[]{1, 2, 4}));
    }

    /**
     * 394 · 硬币排成线
     * 有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。
     * <p>
     * 请判定 先手玩家 必胜还是必败?
     * 若必胜, 返回 true, 否则返回 false.
     * <p>
     * 样例
     * 输入: 1
     * 输出: true
     */
    public boolean firstWillWin(int n) {
        // write your code here
        if (n <= 0) return false;
        /*
        dp[i] 表示前i个硬币，先手必胜（败）
        为了使先手必胜，那么在取走1个或者2个硬币后，造成先手必败，则当前先手必胜
        dp[i - 1] = true dp[i - 2] = true, dp[i] = false 先手必败
        dp[i - 1] = false dp[i - 2] = true, dp[i] = true 先手必胜
        dp[i - 1] = true dp[i - 2] = false, dp[i] = true 先手必胜
        dp[i - 1] = false dp[i - 2] = false, dp[i] = true 先手必胜
        所以 dp[i] = dp[i - 1] == false || dp[i - 2] == false 先手比胜

        初始值：
        dp[0] = dp[1] = true 1 or 2个硬币 先手必胜
         */
        if (n <= 2) return true;
        boolean[] dp = new boolean[n];
        dp[0] = dp[1] = true;
        dp[2] = false;
        for (int i = 3; i < n; i++) {
            if (dp[i - 2] == false || dp[i - 1] == false) {
                dp[i] = true;
            } else {
                dp[i] = false;
            }
        }

        return dp[n - 1];
    }

    /**
     * 395 · 硬币排成线 II
     * 有 n 个不同价值的硬币排成一条线。两个参赛者轮流从 左边 依次拿走 1 或 2 个硬币，直到没有硬币为止。计算两个人分别拿到的硬币总价值，价值高的人获胜。
     * <p>
     * 请判定 先手玩家 必胜还是必败?
     * 若必胜, 返回 true, 否则返回 false.
     * <p>
     * 样例
     * 输入: [1, 2, 2]
     * 输出: true
     * 解释: 先手玩家直接拿走两颗硬币即可.
     */
    public boolean firstWillWin(int[] values) {
        if (values == null || values.length < 3) {
            return true; // 少于2个，先手必胜
        }
        /*
        倒着来...
        dp[i]表示剩余i...n-1个硬币时，先手最大价值
        sum[i] = values[i] + ... valuse[n - 1]
        那么后手的价值为，sum[i] - dp[i]

        dp[i] =
        max( sum[i + 1] - dp[i + 1] + values[i], // 先手者拿一枚
        max( sum[i + 2] - dp[i + 2] + values[i] + values[i + 1], // 先手者拿两枚

        dp[n - 1] = values[n - 1]
        dp[n - 2] = values[n - 1] + values[n - 2]
         */
        int n = values.length;
        int[] sum = new int[n];
        int[] dp = new int[n];
        dp[n - 1] = sum[n - 1] = values[n - 1];
        dp[n - 2] = sum[n - 2] = values[n - 1] + values[n - 2];

        for (int i = n - 3; i >= 0; i --) {
            sum[i] = sum[i + 1] + values[i];
            dp[i] = Math.max(
                    sum[i + 1] - dp[i + 1] + values[i],
                    sum[i + 2] - dp[i + 2] + values[i] + values[i + 1]
            );
        }
        return dp[0] > sum[0] - dp[0];
    }
}
